package NC;

import java.util.ArrayList;
import java.util.Arrays;

// 回溯典型（排列，有重复）
public class NC42 {
    private ArrayList<ArrayList<Integer>> ans = new ArrayList<>();
    public ArrayList<ArrayList<Integer>> permuteUnique(int[] num) {
        Arrays.sort(num);
        backtrace(num,num.length,0,new ArrayList<>(),new boolean[num.length]);
        return ans;
    }
    public void backtrace(int[] num,int leave,int start,ArrayList<Integer> temp,boolean[] used){
        if(leave<0) return;
        if(leave==0) {ans.add(new ArrayList<>(temp)); return;}
        for (int i = 0; i < num.length; i++) {
            if(i>0 &&num[i-1]==num[i] && !used[i-1]) continue; //只能按一个顺序进行访问连续相同的元素，才能保证唯一
            if(used[i]) continue;
            used[i] = true;
            temp.add(num[i]);
            backtrace(num,leave-1,i+1,temp,used);
            temp.remove(temp.size()-1);
            used[i] =false;
        }
    }
}

class Test2{
    public static void main(String[] args) {
        NC42 nc42 = new NC42();
        System.out.println(nc42.permuteUnique(new int[]{1, 1, 2}));
    }
}
